from typing import List

"""
1011. 在 D 天内送达包裹的能力

思路： 运送的能力最小是weights最大的那个元素，最大是整个weights的大小。
如果在里面找到答案，我们假设运送能力为 (运送的最大能力 + 运送的最小能力) // 2

然后累加weights的值，看看能分成多少份，如果 大于D，那么说明在小于等于D，说明区间在[运送的最小能力， mid]
如果大于D， 说明区间在[mid+1, 运送的最大能力]
"""


class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        # 确定二分查找左右边界
        left, right = max(weights), sum(weights)
        while left < right:
            mid = (left + right) // 2
            print(left, right, mid)
            # need 为需要运送的天数
            # cur 为当前这一天已经运送的包裹重量之和
            need, cur = 1, 0
            for weight in weights:
                if cur + weight > mid:
                    need += 1
                    cur = 0
                    print("weight=", weight)
                cur += weight
            print("need=", need)

            if need <= D:
                right = mid
            else:
                left = mid + 1

        return left


if __name__ == "__main__":
    res = Solution().shipWithinDays([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5)
    print(res)